package com.yan_jiu_sheng.LeetCodeHot100.AC;

import java.util.*;

/**
 * https://leetcode.cn/problems/rotting-oranges/description/?envType=study-plan-v2&envId=top-100-liked
 * 参考解析
 *
 * @author yulongTian
 * @create 2024-06-27 13:32
 */
public class Test52 {
    public static void main(String[] args) {
        int[][] grid = {{2, 1, 1}, {1, 1, 0}, {0, 1, 1}};
//        int[][] grid = {{0, 2}};
        System.out.println(new Test52().orangesRotting(grid));
    }

    /**
     * 这种需要一圈一圈往外传播的一般用BFS解， 先找到起始所有腐烂的橘子，然后循环处理，把新腐烂的橘子加入下一次循环的队列中，
     * 当下一次循环的队列为空时，说明不能继续腐烂了， 判断一下还有没有新鲜的橘子，如果有，就返回-1，否则返回分钟数
     * <p>
     * 先遍历统计新鲜数量和腐烂节点，再bfs进行腐烂过程并计时，腐烂结束看看还有没有新鲜橙子
     * <p>
     * 值 0 代表空单元格；
     * 值 1 代表新鲜橘子；
     * 值 2 代表腐烂的橘子。
     *
     * @param grid
     * @return
     */
    public int orangesRotting(int[][] grid) {
        // 统计新鲜橙子
        int freshNum = 0;
        // dfs 统计腐烂橙子
        Deque<int[]> queue = new ArrayDeque<>();
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 1) {
                    freshNum++;
                }
                if (grid[i][j] == 2) {
                    queue.offer(new int[]{i, j});
                }
            }
        }
        int minutes = 0;
        while (!queue.isEmpty()) {
            if (freshNum == 0) {
                // 没有新鲜橙子了
                return minutes;
            }
            // 过去1分钟，周围开始腐烂
            minutes++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] rot = queue.pop();
                int x = rot[0];
                int y = rot[1];
                freshNum -= roting(grid, x - 1, y, queue);
                freshNum -= roting(grid, x + 1, y, queue);
                freshNum -= roting(grid, x, y - 1, queue);
                freshNum -= roting(grid, x, y + 1, queue);
            }
        }
        // 腐烂过程结束
        return freshNum > 0 ? -1 : minutes;
    }

    private int roting(int[][] grid, int x, int y, Deque<int[]> queue) {
        if (x < 0 || y < 0 || x > grid.length - 1 || y > grid[0].length - 1 || grid[x][y] != 1) {
            return 0;
        }
        // grid[x][y] = 1
        grid[x][y] = 2;
        queue.offer(new int[]{x, y});
        return 1;
    }


    /*
    // 自己想的实现方法，本地电脑可以跑出结果 力扣系统出错，超过时间限制
    public int orangesRotting(int[][] grid) {
        //没有腐烂的
        if (!check2(grid)) {
            return -1;
        }
//        if (check(grid)) {
//            //一开始全都腐烂
//            return 0;
//        }
        int ans = 0;
        int m = grid.length;
        int n = grid[0].length;
        Map<Integer, Integer> map = new HashMap<>();
        int count = check(grid);//新鲜的橘子个数

        while (count > 0) {
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == 2) {
                        // 上
                        if (i - 1 >= 0) {
                            if (grid[i - 1][j] == 1) {
                                map.put(i - 1, j);
                            }
                        }
                        // 下
                        if (i + 1 < m) {
                            if (grid[i + 1][j] == 1) {
                                map.put(i + 1, j);
                            }
                        }
                        // 左
                        if (j - 1 >= 0) {
                            if (grid[i][j - 1] == 1) {
                                map.put(i, j - 1);
                            }
                        }
                        // 右
                        if (j + 1 < n) {
                            if (grid[i][j + 1] == 1) {
                                map.put(i, j + 1);
                            }
                        }
                    }
                }
            }
            for (Integer integer : map.keySet()) {
                grid[integer][map.get(integer)] = 2;
                count--;
            }
            map.clear();
            ans++;
        }

        return ans;
    }


    private int check(int[][] grid) {
        int ans = 0;
        int n = grid[0].length;
        for (int[] ints : grid) {
            for (int j = 0; j < n; j++) {
                if (ints[j] == 1) {
                    ans++;
                }
            }
        }
        return ans;
    }

    private boolean check2(int[][] grid) {
        int n = grid[0].length;
        for (int[] ints : grid) {
            for (int j = 0; j < n; j++) {
                if (ints[j] == 2) {
                    return true;// 有腐烂橘子
                }
            }
        }
        return false;//没有腐烂的橘子
    }
*/
}
